第61章 计数原理

计数原理是组合数学的基础，主要研究完成一件事的不同方法的数量计算规则。

61.1 基本计数原理

61.1.1 加法原理(分类计数原理)

定义 若完成一件事有$n$类不同的方法，在第1类方法中有$m_1$种不同的方式，在第2类方法中有$m_2$种不同的方式……在第n类方法中有$m_n$种不同的方式，且这些方法彼此独立（即选择任何一类方法中的任何一种方式都能单独完成这件事），则完成这件事的$总方法数 = m_{1} × m_{2} × ... × m_{n} = m_{1}+m_{2}+...+m_{n}$为各类方法数之和： $总方法数 = m_{1} × m_{2} × ... × m_{n} = m_{1}+m_{2}+...+m_{n} = m_{1}+m_{2}+...+m_{n}$ 核心特征

1. "分类"：各类方法之间是"或"的关系。
2. "互斥"：不同类的方法不能同时使用。

示例 从 A 地到B地，可乘火车、汽车或飞机。火车有3班次，汽车有5班次，飞机有2班次，则从A地到B地的总交通方式有 $3+5+2=10$ 种。

61.1.2 乘法原理(分步计数原理)

定义 若完成一件事需要经过$n$个步骤，完成第1步有$m_1$种不同的方式，完成第2步有$m_2$种不同的方式……完成第n步有$m_n$种不同的方式，且各步骤之间相互依赖（只有完成所有步骤才能完成这件事），则完成这件事的$总方法数 = m_{1} × m_{2} × ... × m_{n} = m_{1}+m_{2}+...+m_{n}$为各步骤方法数的乘积： $总方法数 = m_{1} × m_{2} × ... × m_{n} = m_{1}+m_{2}+...+m_{n} = m_{1} × m_{2} × ... × m_{n}$ 核心特征

1. "分步"：各步骤之间是"且"的关系。
2. "关联"：前一步骤的选择会影响后一步骤的可选项，但不影响方法数的计算。

示例 从 A 地到B地需先乘火车到C地，再乘汽车到B地。从 A 到C的火车有3班次，从C到B的汽车有5班次，则从A地到B地的总交通方式有 $3 ×5=15$ 种。

61.1.3 加法原理与乘法原理的区别

原理	适用场景	逻辑关系	计算方式
加法原理	分类完成，各类方法独立	或(OR)	求和
乘法原理	分步完成，各步骤依赖	且 (AND)	求积

61.2 排列

61.2.1 定义

排列是指从 n 个不同元素中，取出 k 个元素 $(1 ≤k ≤n)$，按照一定的顺序排成一列，称为从 $n$ 个不同元素中取出k个元素的一个排列。所有可能的排列的数量称为排列数，记作 $P(n, k)$或 $A(n, k)$。

61.2.2 计算公式

排列数公式： $P(n, k)=n \times(n-1) \times(n-2) × \cdots \times(n-k+1)$ 阶乘表示：由于 $n! =n \times(n-1) ×\cdots ×1$（$n$的阶乘），排列数可表示为： $P(n, k)=\frac{n !}{(n-k) !}$ 规定 $0 !=1$，当 $k=n$ 时，$P(n, n)=n !$。

61.2.3 示例

从5名同学中选3人站成一排拍照，不同的排列方式有： $P(5,3)=5 ×4 ×3=60$ 种。 3个不同的数字全排列 $(k=n=3)$：$P(3,3)=3 !=6$ 种（即123、132、213、231、312、321）。

61.2.4 关键特征

有序性：排列中元素的顺序不同则视为不同的排列（如 "ab" 与 "ba" 是两个不同的排列）。 无重复：取出的k个元素必须互不相同。

61.3 组合

61.3.1 定义

组合是指从n个不同元素中，取出k个元素 $(1 ≤k ≤n)$，不考虑元素的顺序组成一组，称为从 n 个不同元素中取出k个元素的一个组合。所有可能的组合的数量称为组合数，记作 $C(n, k)$。

61.3.2 计算公式

组合数与排列数的区别在于"无序"，因此组合数等于排列数除以 k 个元素的全排列数： $C(n, k)=\frac{P(n, k)}{P(k, k)}=\frac{n !}{k ! \times(n-k) !}$ 性质：

1. $C(n, k)=C(n, n-k)$
2. $C(n, 0)=1$，$C(n, n)=1$

61.3.3 示例

从5名同学中选3人参加座谈会，不同的选法有： $C(5,3)=\frac{5 !}{3 ! × 2 !}=\frac{5 × 4 × 3}{3 × 2 × 1}=10$ 种。 从4个元素中选2个的组合数： $C(4,2)=6$ 种（ab、ac、ad、bc、bd、cd）。

61.3.4 关键特征

无序性：组合中元素的顺序不影响结果（如"ab"与"ba"是同一个组合）。 无重复：取出的k个元素必须互不相同。

61.4 排列与组合的区别

类型	核心特点	公式	示例($n=2,k=2$)
排列	考虑顺序	$P(n, k)=\frac{n!}{(n-k)!}$	ab、ba 共2种
组合	不考虑顺序	$C(n, k)=\frac{n!}{k!(n-k)!}$	a,b 共1种

61.5 常见计数场景与技巧

61.5.1 有限制条件的计数

特殊元素优先法 当某些元素有特殊位置要求时，先安排特殊元素，再处理其他元素。 示例：用09这10个数字组成无重复数字的三位数，百位不能为0。 解法：先选百位（9种选择：19），再选十位9种选择，最后选个位8种选择，总个数为 $9 ×9 ×8=648$。

排除法 先计算无限制条件的$总方法数 = m_{1} × m_{2} × ... × m_{n} = m_{1}+m_{2}+...+m_{n}$，再减去不符合条件的方法数。 示例：从5名同学中选3人参加活动，甲不能参加。 解法：总选法 $C(5,3)=10$，甲必选的选法 $C(4,2)=6$，符合条件选法 $10-6=4$。

61.5.2 可重复元素的计数

可重复排列：从 $n$ 个不同元素中取出k个，允许重复，排列数 $n^k$。 示例：3位数字密码，每位0~9，总数 $10^3=1000$。

可重复组合：从 $n$ 个不同元素取k个可重复，组合数 $C(n+k-1, k)$。 示例：5个相同苹果分给3个小朋友，分法 $C(5+3-1,5)=C(7,5)=21$。

61.5.3 分步与分类综合应用

先分类，每一类内部分步计算，最后用加法汇总。 示例：A到B可选飞机(2)、火车(3)、汽车(5)；B到C火车4或汽车6。 飞机路线：$2 \times (4+6)=20$ 火车路线：$3 \times (4+6)=30$ 汽车路线：$5 \times (4+6)=50$ 总方式：$20+30+50=100$

61.6 计数原理在编程中的应用

适用场景：算法复杂度计算、排列组合求值、概率统计。

61.6.1 C++代码（阶乘、排列、组合）

#include<iostream>
using namespace std;

//计算阶乘
long long factorial(int n){
    long long res=1;
    for (int i=2;i<=n;++i){
        res*=i;
    }
    return res;
}

//计算排列 P(n, k)
long long permutation(int n, int k) {
    if (k<0 || k>n) return 0;
    long long res=1;
    for (int i=0;i<k;++i){
        res*=(n -i);
    }
    return res;
}

//计算组合 C(n, k)
long long combination(int n, int k){
    if (k<0 || k>n) return 0;
    if (k>n-k) k=n-k;
    long long res=1;
    for (int i=1;i<=k; ++i) {
        res=res*(n-k+i)/i;
    }
    return res;
}

int main(){
    cout <<"5! = "<< factorial(5) << endl;
    cout <<"P(5, 3) = "<< permutation (5, 3) << endl;
    cout << "C(5, 3)="<< combination(5, 3) <<endl;
    return 0;
}